package JZ_Offer.dataStructure.tree;

import base.TreeNode;

/**
 * 判断是不是平衡二叉树
 *
 * 输入一棵二叉树，判断该二叉树是否是平衡二叉树。
 * 在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
 * <p>
 * 平衡二叉树定义：平衡二叉树的左右子树也是平衡二叉树，那么所谓平衡就是左右子树的高度差不超过1.
 */
public class JZ79_判断是不是平衡二叉树 {

    private static int depth(TreeNode root) {
        if (root == null) return 0;
        int leftDepth = depth(root.left);
        if (leftDepth == -1) return -1;
        int rightDepth = depth(root.right);
        if (rightDepth == -1) return -1;

        if (leftDepth - rightDepth > 1 || leftDepth - rightDepth < -1) {
            return -1;
        }

        return 1 + (leftDepth > rightDepth ? leftDepth : rightDepth);
    }

    public static boolean IsBalanced_Solution(TreeNode root) {
        return depth(root) != -1;
    }

    public static void main(String[] args) {
    }
}
